//
//  TrieTree.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2021/1/14.
//

class TrieTree {
    static var root: TrieNode = TrieNode(data: "#") // 根节点，存储无意义字符
    
    /// 往trie树中插入字符串
    /// - Parameter string: 需要插入的字符串
    class func insertString(_ string: String){
        let a_ascii = Character("a").asciiValue
        var p: TrieNode = root
        
        for char in string {
            let cha = char as Character
            let cha_ascii = cha.asciiValue
            let index = Int(cha_ascii! - a_ascii!)
            if p.children[index] == nil {
                let newNode = TrieNode(data: cha)
                p.children[index] = newNode
            }
            p = p.children[index]!
        }
        p.isEndingChar = true
    }
    
    /// 在trie树中查找字符串
    /// - Parameter string: 要查找的字符串
    /// - Returns: 返回查询结果
    class func findString(_ string: String) -> Bool{
        let a_ascii = Character("a").asciiValue
        var p: TrieNode = root
        for char in string {
            let cha = char as Character
            let cha_ascii = cha.asciiValue
            let index = Int(cha_ascii! - a_ascii!)
            if p.children[index] == nil {
                return false
            }
            p = p.children[index]!
        }
        
        return p.isEndingChar// isEnding为false,说明不完全匹配,只是前缀
    }
    
}

struct TrieNode {
    var data: Character
    var children = [TrieNode?](repeating: nil, count: 26)
    var isEndingChar: Bool = false
}
